Introduction, number systems, measuring error

Mathematically correct != numerically sound. Using Tolerance:

double x = 1.0;
double y = x / 3.0;
if(fabs(x-y*3.0) < numeric_limits<double>::epsilon()){
    cout << "They are equal" << endl;
}
else
    cout << "They are not equal" << endl;

Sources of Error

• Rounding
  • example: Using IEEE 754
• Discretization
• Modeling
  • Example: Neglecting butterfly wing flapping in a weather model
• Input
  • Example: Measuring error for initial conditions in physical system

Absolute vs. Relative Error

• Absolute Error: The difference between the approximate value and the underlying true value
• Relative Error: Absolute error divided by the true value

Relative Error: Difficulty

Problem: Generally not computable Common fix: Be conservative

Computable Measures of Success

Root-finding problem: For \(f: \mathbb{R} \rightarrow \mathbb{R}\), find \(x^*\) such that \(f(x^*) = 0\). Actual output: \(x_{est}\) with \(|f(x_{est})| <<1\).

Backward Error

The amount the problem statement would have to change to make the approximate solution exact.

Conditioning

• Well conditioned: Small backward error \(\xRightarrow{}\) small relative error
• Poorly conditioned: Otherwise
• Condition number: Ratio of forward to backward error (we want it to be small)
  • Root-finding example: \(\frac{1}{|f'(x^*)|}\)

Example: \(||x||_2\)

double normSquared = 0;
for(int i = 0; i < n; i++){
    normSquared += x[i]*x[i];
}
return sqrt(normSquared);

Overflow, underflow.

Improved \(||x||_2\)

double maxElement = epsilon;
for(int i = 0; i < n; i++){
    maxElement = max(maxElement, fabs(x[i]));
}

for(int i = 0; i < n; i++){
    double scaled = x[i]/maxElement;
    normSquared += scaled*scaled;
}
return sqrt(normSquared)*maxElement;

Motivation for Kahan Algorithm

\[ ((a+b) - a) - b \xlongequal{?} 0 \] Store compensation value!